|
Memory bound refers to a situation in which the time to complete a given computational problem is decided primarily by the amount of memory required to hold data. In other words, the limiting factor of solving a given problem is the memory access speed. The application of memory bound functions could prove to be valuable in preventing spam, which has become a problem of epidemic proportions on the Internet. ==Memory bound functions and memory functions== Memory bound functions and memory functions are related in that both involve extensive memory access, but a distinction exists between the two. Memory functions use a dynamic programming technique called memoization in order to relieve the inefficiency of recursion that might occur. It is based on the simple idea of calculating and storing solutions to subproblems so that the solutions can be reused later without recalculating the subproblems again. The best known example that takes advantage of memoization is an algorithm that computes the Fibonacci numbers. The following pseudocode illustrates an algorithm that uses memoization, which runs in linear CPU time: Fibonacci (n) Fibonacci_Results (results, n) Compare the above to an algorithm that uses recursion, which runs in exponential CPU time: Recursive_Fibonacci (n) While the recursive algorithm is simpler and more elegant than the algorithm that uses memoization, the latter has a significantly lower time complexity than the former. The term "memory bound function" has surfaced only recently and is used principally to describe a function that uses XOR and consists of a series of computations in which each computation depends on the previous computation. Whereas memory functions have long been an important actor in improving time complexity, memory bound functions have seen far fewer applications. Recently, however, scientists have proposed a method using memory bound functions as a means to discourage spammers from abusing resources, which could be a major breakthrough in that area. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「memory bound function」の詳細全文を読む スポンサード リンク
|